package com.my.leetcode;


import java.math.BigDecimal;
import java.util.*;

public class UnknowLabelProblems {


    public static void main(String[] args) {

        UnknowLabelProblems unknowLabelProblems = new UnknowLabelProblems();

    }






    public int hammingWeight(int n) {


        int count = 0;
        for(int i = 0;i < 32;i++){
            int a = 1 << i;
            //System.out.println("a is:=====" + a + "    n & a=" + (n & a));
            if((n & (1 << i)) != 0){
                count ++;
            }
        }
        return count;
    }


    public int hamingWeight(int n){
        int a = 1, count = 0;
        for(int t = 1;t <= 32;t++){
            //System.out.println("a is:=====" + a + "    n & a=" + (n & a));
            if((n & a) != 0) {
                count ++;
            }
            a = a << 1;
        }
        return count;
    }

    /**
     * @author zlx
     * @Description 866. 回文素数 middle
     * 求出大于或等于 N 的最小回文素数。
     *
     * 回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。
     *
     * 例如，2，3，5，7，11 以及 13 是素数。
     *
     * 回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。
     *
     * 例如，12321 是回文数。
     *
     *
     *
     * 示例 1：
     *
     * 输入：6
     * 输出：7
     * 示例 2：
     *
     * 输入：8
     * 输出：11
     * 示例 3：
     *
     * 输入：13
     * 输出：101
     *
     *
     * 提示：
     *
     * 1 <= N <= 10^8
     * 答案肯定存在，且小于 2 * 10^8。
     * @Date 1/7/21
     * @Param [N]
     * @return int
     **/
    public int primePalindrome(int N) {

        if(N >= 8 && N <= 11){
            return 11;
        }
        for(int i= 1;i < 100000;i++){

            String s = Integer.toString(i), r = new StringBuilder(s).reverse().toString();
            int y = Integer.parseInt(s + r.substring(1));
            if (y >= N && isPrime(y))
                return y;
        }
        return -1;
    }

    public boolean isPrime(int n){

        if(n < 2 || n % 2 == 0){
            return n == 2;
        }
        for(int i = 3;i * i <= n;i +=2){

            if(n % i == 0){
                return false;
            }
        }
        return true;
    }


    /**
     * @author zlx
     * @Description 509. 斐波那契数
     * 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
     *
     * F(0) = 0，F(1) = 1
     * F(n) = F(n - 1) + F(n - 2)，其中 n > 1
     * 给你 n ，请计算 F(n) 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：2
     * 输出：1
     * 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
     * 示例 2：
     *
     * 输入：3
     * 输出：2
     * 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
     * 示例 3：
     *
     * 输入：4
     * 输出：3
     * 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
     *
     *
     * 提示：
     *
     * 0 <= n <= 30
     * @Date 1/7/21
     * @Param [n]
     * @return int
     **/
    public int fib(int n) {

        if(n <= 1){
            return n;
        }

        int [] fib = new int[n + 1];
        fib[1] = 1;
        for(int i = 2;i <= n;i++){
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib[n];
    }

    public int smallestRepunitDivByK(int K) {

        if(K % 2 == 0 || K % 5 == 0){
            return -1;
        }

        int temp = 1;
        int len = 1;
        while (temp % K != 0){
            temp = temp % K;
            temp = temp * 10 + 1;
            len ++;
        }
        return len;
    }


    /**
     * @author zlx
     * @Description 738. 单调递增的数字 middle
     * 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
     *
     * （当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
     *
     * 示例 1:
     *
     * 输入: N = 10
     * 输出: 9
     * 示例 2:
     *
     * 输入: N = 1234
     * 输出: 1234
     * 示例 3:
     *
     * 输入: N = 332
     * 输出: 299
     * 说明: N 是在 [0, 10^9] 范围内的一个整数。
     *
     * 解题思路：基于贪心思想，找到第一个递减的位置i， [0,i-1]是递增序列，chars[i-1] >chars[i]，为了得到小于或等于N的最大单调递增整数，不考虑位数，使i后面的值为9
     * 从贪心角度考虑，还要尽量让高位与N的位数相等，因此让chars[i-1]--, 所以chars[i]到chars[n-1]= 9
     * 存在的问题是： chars[i-1]-- 后，chars[i-2], chars[i-1]可能不是递增关系了，因此需要在0到i-1找到j，j+1之后的数全部置为9，
     *
     * @Date 2020-12-15
     * @Param [N]
     * @return int
     **/
    public int monotoneIncreasingDigits(int N) {

        char [] chars = Integer.toString(N).toCharArray();
        int i = 1;
        //找第一个递减的位置
        while (i < chars.length && chars[i-1] <= chars[i]){
            i++;
        }

        if(i < chars.length){

            //从原来递增串中找j，0到j是递增
            while (i > 0 && chars[i-1] > chars[i]){
                chars[i-1]--;
                i = i-1;
            }
            //j+1 到 len-1 置为9
            for(int j = i+1;j < chars.length;j++){
                chars[j] = '9';
            }
        }

        return Integer.parseInt(new String(chars));

    }

    /**
     * @author zlx
     * @Description 134. 加油站
     * 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
     *
     * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
     *
     * 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
     *
     * 说明:
     *
     * 如果题目有解，该答案即为唯一答案。
     * 输入数组均为非空数组，且长度相同。
     * 输入数组中的元素均为非负数。
     * 示例 1:
     *
     * 输入:
     * gas  = [1,2,3,4,5]
     * cost = [3,4,5,1,2]
     *
     * 输出: 3
     *
     * 解释:
     * 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
     * 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
     * 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
     * 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
     * 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
     * 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
     * 因此，3 可为起始索引。
     * 示例 2:
     *
     * 输入:
     * gas  = [2,3,4]
     * cost = [3,4,3]
     *
     * 输出: -1
     *
     * 解释:
     * 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
     * 我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
     * 开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
     * 开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
     * 你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
     * 因此，无论怎样，你都不可能绕环路行驶一周。
     *
     * 解题思路： 能绕环一周，gas[start] + …… + gas[i] + …… + gas[start-1] >= cost[start] + …… + cost[i] + …… + cost[start-1]
     * @Date 2020-11-18
     * @Param [gas, cost]
     * @return int
     **/
    public int canCompleteCircuit(int[] gas, int[] cost) {

        int n = gas.length;
        int i = 0;
        while (i < n){
            int sumGas = 0, sumCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumCost += cost[j];
                sumGas += gas[j];
                if (sumCost > sumGas) {
                    break;
                }
                cnt ++;
            }

            if(cnt == n){
                return i;
            }else{
                i = i + cnt + 1;
            }
        }

        return -1;
    }

    /**
     * @author zlx
     * @Description 经过求导和微分，尽量3等分，乘积最大
     * @Date 2020-11-16
     * @Param [n]
     * @return int
     **/
    public int cuttingRope(int n) {

        if(n <= 3){
            return n-1;
        }

        int a = n/3, b= n %3;
        if(b== 0){

            return (int)Math.pow(3, a);
        }else if(b == 1){

            return (int)Math.pow(3, a-1) * 4;
        }else{
            return (int)Math.pow(3, a) * 2;
        }
    }


    /**
     * @author zlx
     * @Description 922. 按奇偶排序数组 II easy
     * 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
     *
     * 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
     *
     * 你可以返回任何满足上述条件的数组作为答案。
     *
     *
     *
     * 示例：
     *
     * 输入：[4,2,5,7]
     * 输出：[4,5,2,7]
     * 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
     *
     *
     * 提示：
     *
     * 2 <= A.length <= 20000
     * A.length % 2 == 0
     * 0 <= A[i] <= 1000
     *
     * @Date 2020-11-12
     * @Param [A]
     * @return int[]
     **/
    public int[] sortArrayByParityII(int[] A) {

        for(int i = 0;i < A.length-1;i++){

            if(i%2 == 0){
                if(A[i] % 2 == 0){
                    continue;
                }else{
                    for(int j = i+1;j < A.length;j++){
                        if(A[j] % 2 == 0){
                            swap(A, i, j);
                            break;
                        }
                    }
                }
            }else{

                if(A[i]%2 == 1){
                    continue;
                }else{

                    for(int j = i+1;j < A.length;j++){

                        if(A[j]%2 == 1){
                            swap(A, i,j);
                            break;
                        }
                    }
                }
            }
        }
        return A;
    }

    /**
     * @author zlx
     * @Description 31. 下一个排列 middle
     * 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
     *
     * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
     *
     * 必须原地修改，只允许使用额外常数空间。
     *
     * 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
     * 1,2,3 → 1,3,2
     * 3,2,1 → 1,2,3
     * 1,1,5 → 1,5,1
     * @Date 2020-11-11
     * @Param [nums]
     * @return void
     **/
    public void nextPermutation(int[] nums) {

        if(nums == null || nums.length <= 0){
            return ;
        }

        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i+1]){
            i--;
        }

        if(i >= 0){

            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]){
                j--;
            }

            swap(nums, i, j);
        }

        reverse(nums, i+1);
    }

    public void reverse(int [] nums, int start){

        int end = nums.length - 1;
        while (start < end){

            swap(nums, start, end);
            start++;
            end --;
        }
    }

    public void swap(int [] nums, int i, int j){

        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }


    /**
     * @author zlx
     * @Description 910. 最小差值 II middle
     * 给定一个整数数组 A，对于每个整数 A[i]，我们可以选择 x = -K 或是 x = K，并将 x 加到 A[i] 中。
     *
     * 在此过程之后，我们得到一些数组 B。
     *
     * 返回 B 的最大值和 B 的最小值之间可能存在的最小差值。
     *
     *
     *
     * 示例 1：
     *
     * 输入：A = [1], K = 0
     * 输出：0
     * 解释：B = [1]
     * 示例 2：
     *
     * 输入：A = [0,10], K = 2
     * 输出：6
     * 解释：B = [2,8]
     * 示例 3：
     *
     * 输入：A = [1,3,6], K = 3
     * 输出：3
     * 解释：B = [4,6,3]
     * @Date 2020-09-27
     * @Param [A, K]
     * @return int
     **/
    public int smallestRangeII(int[] A, int K) {

        Arrays.sort(A);
        // 注意这里有个特殊情况，就是我们压根“不切这一刀”，而是把整个数组全部上移或下移，这也是一种策略。这种策略下的差值是 A[len - 1] - A[0]
        int res = A[A.length - 1] - A[0];
        for(int i = 0;i < A.length - 1;i++){
            int tmp = Math.max(A[i] + K, A[A.length - 1] - K) - Math.min(A[0] + K, A[i+1] - K);
            res = Math.min(res, tmp);
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 908. 最小差值 I easy
     * 给你一个整数数组 A，请你给数组中的每个元素 A[i] 都加上一个任意数字 x （-K <= x <= K），从而得到一个新数组 B 。
     *
     * 返回数组 B 的最大值和最小值之间可能存在的最小差值。
     *
     *
     *
     * 示例 1：
     *
     * 输入：A = [1], K = 0
     * 输出：0
     * 解释：B = [1]
     * 示例 2：
     *
     * 输入：A = [0,10], K = 2
     * 输出：6
     * 解释：B = [2,8]
     * 示例 3：
     *
     * 输入：A = [1,3,6], K = 3
     * 输出：0
     * 解释：B = [3,3,3] 或 B = [4,4,4]
     *
     *
     * 提示：
     *
     * 1 <= A.length <= 10000
     * 0 <= A[i] <= 10000
     * 0 <= K <= 10000
     * @Date 2020-09-27
     * @Param [A, K]
     * 为了使得 max(B) - min(B) 最小， max(B)变化之后的最小值， min(B) 是变化之后的最大值
     * max(B)中的最小值= max(A) - K
     * min(B)的最大值=min(A) + K
     *
     * 如果 A[i] <= min(A) + K  那么 B[i] = min(A) + K
     * 如果 A[i] >= max(A)-K，那么 B[i] = max(A) - K
     * 否则 B[i] = A[i]
     * @return int
     **/
    public int smallestRangeI(int[] A, int K) {

        Arrays.sort(A);
        int res = A[A.length - 1] - A[0] - 2 * K;
        return res < 0 ? 0 : res;
    }

    /**
     * @author zlx
     * @Description 29. 两数相除 middle
     * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
     *
     * 返回被除数 dividend 除以除数 divisor 得到的商。
     *
     * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
     *
     *
     *
     * 示例 1:
     *
     * 输入: dividend = 10, divisor = 3
     * 输出: 3
     * 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
     * 示例 2:
     *
     * 输入: dividend = 7, divisor = -3
     * 输出: -2
     * 解释: 7/-3 = truncate(-2.33333..) = -2
     *
     *
     * 提示：
     *
     * 被除数和除数均为 32 位有符号整数。
     * 除数不为 0。
     * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
     *
     *
     * 不用乘除法+mod计算两数相除，第一反应是位运算，本解法使用的是减法+比较
     * @Date 2020-09-23
     * @Param [dividend, divisor]
     * @return int
     **/
    public int divide(int dividend, int divisor) {

        if(dividend == 0){
            return 0;
        }

        if(divisor == 1){
            return dividend;
        }

        if(divisor == -1){
            if(dividend == Integer.MIN_VALUE){
                return Integer.MAX_VALUE;
            }
            return -dividend;
        }

        int sign = 1;
        if((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)){
            sign = -1;
        }

        long a = dividend;
        long b = divisor;
        a = a > 0 ? a : -a;
        b = b > 0 ? b : -b;

        int res = divd(a, b);

        System.out.println("res is:=====" + res);

        if(sign == -1){
            res = (res == Integer.MAX_VALUE ? Integer.MIN_VALUE : -res);
        }

        return res;
    }

    public int divd(long a, long b){

        System.out.println("a is: ====" + a + "     b is:  " + b);

        if(a < b){
            return 0;
        }
        long tb = b;
        int count = 1;
        while ((tb + tb) < a){

            count = count + count;
            tb = tb + tb;
        }
        return count + divd(a - tb, b);
    }

    //此方法求除数会内存溢出
    public int divde(long a, long b){

        if(a < b){
            return 0;
        }

        int count = 1;
        return count + divde(a - b, b);
    }



    /**
     * @author zlx
     * @Description 216. 组合总和 III   middle
     * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
     *
     * 说明：
     *
     * 所有数字都是正整数。
     * 解集不能包含重复的组合。
     * 示例 1:
     *
     * 输入: k = 3, n = 7
     * 输出: [[1,2,4]]
     * 示例 2:
     *
     * 输入: k = 3, n = 9
     * 输出: [[1,2,6], [1,3,5], [2,3,4]]
     * @Date 2020-09-11
     * @Param [k, n]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    public List<List<Integer>> combinationSum3(int k, int n) {

        if(k <= 0){
            return null;
        }
        int [] candidates = new int[9];
        for(int i = 0;i < candidates.length;i++){
            candidates[i] = i+1;
        }

        onCombine = new ArrayList<>();
        combines = new ArrayList<>();

        trackingSums3(k, n ,0, 0);
        return combines;
    }

    public void  trackingSums3(int k, int n, int index, int sum){

        if(sum > n || onCombine.size() > k){
            return ;
        }
        if(sum == n && onCombine.size() == k){
            combines.add(new ArrayList<>(onCombine));
        }
        for(int i = index+1;i <= 9;i++){
            onCombine.add(i);
            trackingSums3(k, n, i, sum+ i);
            onCombine.remove(onCombine.size() - 1);
        }
    }


    

    /**
     * @author zlx
     * @Description 40. 组合总和 II
     * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     *
     * candidates 中的每个数字在每个组合中只能使用一次。
     *
     * 说明：
     *
     * 所有数字（包括目标数）都是正整数。
     * 解集不能包含重复的组合。
     * 示例 1:
     *
     * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
     * 所求解集为:
     * [
     *   [1, 7],
     *   [1, 2, 5],
     *   [2, 6],
     *   [1, 1, 6]
     * ]
     * 示例 2:
     *
     * 输入: candidates = [2,5,2,1,2], target = 5,
     * 所求解集为:
     * [
     *   [1,2,2],
     *   [5]
     * ]
     * @Date 2020-09-11
     * @Param [candidates, target]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        if(candidates == null || candidates.length <= 0){
            return null;
        }
        Arrays.sort(candidates);
        onCombine = new ArrayList<>();
        combines = new ArrayList<>();
        boolean [] flag = new boolean[candidates.length];
        trackingCandidates22(candidates, target, 0, -1);
        //trackingCandidates(candidates, target, 0, flag, 0);
        return combines;
    }

    public void trackingCandidates(int [] candidates, int target, int sum, boolean[] flag, int index){

        if(sum > target){
            return ;
        }
        if(target == sum){
            if(!combines.contains(new ArrayList<>(onCombine))){
                System.out.println("--------------------");
                combines.add(new ArrayList<>(onCombine));
            }

        }

        for(int i =index;i < candidates.length;i++){
            if(!flag[i]){
                flag[i] = true;
                onCombine.add(candidates[i]);
                trackingCandidates(candidates, target, sum + candidates[i], flag, i);
                flag[i] = false;
                onCombine.remove(onCombine.size() - 1);
            }
        }
    }

    public void trackingCandidates22(int [] candidates, int target, int sum, int index){

        if(sum > target){
            return ;
        }
        if(target == sum){
            if(!combines.contains(new ArrayList<>(onCombine))){
                System.out.println("--------------------");
                combines.add(new ArrayList<>(onCombine));
            }

        }
        for(int i =index + 1;i < candidates.length;i++){
                onCombine.add(candidates[i]);
                trackingCandidates22(candidates, target, sum + candidates[i], i);
                onCombine.remove(onCombine.size() - 1);
        }
    }
    /**
     * @author zlx
     * @Description 39. 组合总和 middle
     * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     *
     * candidates 中的数字可以无限制重复被选取。
     *
     * 说明：
     *
     * 所有数字（包括 target）都是正整数。
     * 解集不能包含重复的组合。
     * 示例 1：
     *
     * 输入：candidates = [2,3,6,7], target = 7,
     * 所求解集为：
     * [
     *   [7],
     *   [2,2,3]
     * ]
     * 示例 2：
     *
     * 输入：candidates = [2,3,5], target = 8,
     * 所求解集为：
     * [
     *   [2,2,2,2],
     *   [2,3,3],
     *   [3,5]
     * ]
     *
     *
     * 提示：
     *
     * 1 <= candidates.length <= 30
     * 1 <= candidates[i] <= 200
     * candidate 中的每个元素都是独一无二的。
     * 1 <= target <= 500
     *
     * 解题思路：回溯法求解
     *
     * @Date 2020-09-09
     * @Param [candidates, target]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        if(candidates == null || candidates.length <= 0){
            return null;
        }
        Set<Integer> candidatesSet = new HashSet<>();
        for(int i : candidates){
            candidatesSet.add(i);
        }
        combines = new ArrayList<>();
        onCombine = new ArrayList<>();
        //dfsCombination(candidates, target, 0);
        dfsCombinationII(candidates, target, 0, 0);

        return combines;
    }


    //回溯法+剪枝
    public void dfsCombinationII(int [] candidates, int target, int sum, int index){

        if(sum > target){
            return;
        }
        if(sum == target){
            combines.add(new ArrayList<>(onCombine));
            return;
        }

        for(int i = index;i < candidates.length;i++){
            int val = candidates[i];
            onCombine.add(val);
            dfsCombinationII(candidates, target, sum + val,i);
            onCombine.remove(onCombine.size() - 1);
        }
    }

    //回溯法
    public void dfsCombination(int [] candidates, int target, int sum){

        if(sum > target){
            return;
        }
        if(sum == target){
            combines.add(new ArrayList<>(onCombine));
            return;
        }

        for(int i : candidates){
            if(onCombine.isEmpty() || onCombine.get(onCombine.size() - 1) <= i) {
                onCombine.add(i);
                dfsCombination(candidates, target, sum + i);
                onCombine.remove(onCombine.size() - 1);
            }
        }

    }

    /**
     * @author zlx
     * @Description 77. 组合 middle
     * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
     *
     * 示例:
     *
     * 输入: n = 4, k = 2
     * 输出:
     * [
     *   [2,4],
     *   [3,4],
     *   [2,3],
     *   [1,2],
     *   [1,3],
     *   [1,4],
     * ]
     *
     * 解题思路： 基于回溯法进行求解
     * @Date 2020-09-08
     * @Param [n, k]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    public List<List<Integer>> combine(int n, int k) {

        if(k <= 0){
            return null;
        }
        boolean [] flags = new boolean[n];
        combines = new ArrayList<>();
        onCombine = new ArrayList<>();
        tracking(flags, 0, k, n);
        return combines;

    }

    public static List<List<Integer>> combines = new ArrayList<>();
    public static List<Integer> onCombine = new ArrayList<>();

    public void tracking(boolean[] flags, int index, int k, int n){

        if(onCombine.size() == k){
            List<Integer> tmp = new ArrayList<>();
            for(Integer i : onCombine){
                tmp.add(i);
            }
            combines.add(tmp);
            return ;
        }

        for(int i = index;i < n;i++){
            if(!flags[i]){
                if(onCombine.isEmpty() || onCombine.get(onCombine.size() - 1) < (i+1)) {
                    onCombine.add(i + 1);
                    flags[i] = true;
                    tracking(flags, index + 1, k, n);
                    onCombine.remove(onCombine.size() - 1);
                    flags[i] = false;
                }
            }
        }

    }




    /**
     * @author zlx
     * @Description 60. 第k个排列 middle
     * 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
     *
     * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
     *
     * "123"
     * "132"
     * "213"
     * "231"
     * "312"
     * "321"
     * 给定 n 和 k，返回第 k 个排列。
     *
     * 说明：
     *
     * 给定 n 的范围是 [1, 9]。
     * 给定 k 的范围是[1,  n!]。
     * 示例 1:
     *
     * 输入: n = 3, k = 3
     * 输出: "213"
     * 示例 2:
     *
     * 输入: n = 4, k = 9
     * 输出: "2314"
     *
     *
     * 解题思路：直接用回溯法做的话需要在回溯到第k个排列时终止就不会超时了, 但是效率依旧感人
     *         可以用数学的方法来解, 因为数字都是从1开始的连续自然数, 排列出现的次序可以推
     *         算出来, 对于n=4, k=15 找到k=15排列的过程:
     *
     *         1 + 对2,3,4的全排列 (3!个)
     *         2 + 对1,3,4的全排列 (3!个)         3, 1 + 对2,4的全排列(2!个)
     *         3 + 对1,2,4的全排列 (3!个)-------> 3, 2 + 对1,4的全排列(2!个)-------> 3, 2, 1 + 对4的全排列(1!个)-------> 3214
     *         4 + 对1,2,3的全排列 (3!个)         3, 4 + 对1,2的全排列(2!个)         3, 2, 4 + 对1的全排列(1!个)
     *
     *         确定第一位:
     *             k = 14(从0开始计数)
     *             index = k / (n-1)! = 2, 说明第15个数的第一位是3
     *             更新k
     *             k = k - index*(n-1)! = 2
     *         确定第二位:
     *             k = 2
     *             index = k / (n-2)! = 1, 说明第15个数的第二位是2
     *             更新k6
     *             k = k - index*(n-2)! = 0
     *         确定第三位:
     *             k = 0
     *             index = k / (n-3)! = 0, 说明第15个数的第三位是1
     *             更新k
     *             k = k - index*(n-3)! = 0
     *         确定第四位:
     *             k = 0
     *             index = k / (n-4)! = 0, 说明第15个数的第四位是4
     *         最终确定n=4时第15个数为3214
     *
     * @Date 2020-09-05
     * @Param [n, k]
     * @return java.lang.String
     **/
    public String getPermutation(int n, int k) {

        StringBuilder sb = new StringBuilder();
        List<Integer> array = new ArrayList<>();
        for(int i = 1;i <= n;i++){
            array.add(i);
        }

        int [] factorial = new int[n + 1];
        factorial[0] = 1;
        for(int i = 1;i <=n;i++){
            factorial[i] = factorial[i - 1] * i;
        }

        k--;
        for(int i = 1;i <=n;i++){

            int index = k/factorial[n - i];
            sb.append(array.get(index).toString());
            array.remove(index);
            k -= factorial[n - i] * index;
        }

        System.out.println("res is:====" + sb.toString());

        return sb.toString();
    }


    /**
     * @author zlx
     * @Description easy
     * @Date 2020-08-31
     * @Param [moves]
     * @return boolean
     **/
    public boolean judgeCircle(String moves) {

        if(moves == null){
            return true;
        }
        Map<Character, Integer> map = new HashMap<>();
        map.put('R', 0);
        map.put('D', 1);
        map.put('L', 2);
        map.put('U', 3);

        int [][] directions = {{0, 1}, {1,0}, {0, -1}, {-1, 0}};

        int startX = 0, startY = 0;
        for(int i = 0;i < moves.length();i++){
            Integer tmp = map.get(moves.charAt(i));
            startX = startX + directions[tmp][0];
            startY = startY + directions[tmp][1];
        }

        return (startX == 0 && startY == 0);
    }


    /**
     * @author zlx
     * @Description 1025. 除数博弈
     * 爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
     *
     * 最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
     *
     * 选出任一 x，满足 0 < x < N 且 N % x == 0 。
     * 用 N - x 替换黑板上的数字 N 。
     * 如果玩家无法执行这些操作，就会输掉游戏。
     *
     * 只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
     *
     *
     *
     * 示例 1：
     *
     * 输入：2
     * 输出：true
     * 解释：爱丽丝选择 1，鲍勃无法进行操作。
     * 示例 2：
     *
     * 输入：3
     * 输出：false
     * 解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
     *
     *
     * 解题思路：找规律
     *
     * 博弈类的问题常常让我们摸不着头脑。当我们没有解题思路的时候，不妨试着写几项试试：
     *
     * N = 1N=1 的时候，区间 (0, 1)(0,1) 中没有整数是 nn 的因数，所以此时 Alice 败。
     * N = 2N=2 的时候，Alice 只能拿 11，NN 变成 11，Bob 无法继续操作，故 Alice 胜。
     * N = 3N=3 的时候，Alice 只能拿 11，NN 变成 22，根据 N = 2N=2 的结论，我们知道此时 Bob 会获胜，Alice 败。
     * N = 4N=4 的时候，Alice 能拿 11 或 22，如果 Alice 拿 11，根据 N = 3N=3 的结论，Bob 会失败，Alice 会获胜。
     * N = 5N=5 的时候，Alice 只能拿 11，根据 N = 4N=4 的结论，Alice 会失败。
     * ......
     * 写到这里，也许你有了一些猜想。没关系，请大胆地猜想，在这种情况下大胆地猜想是 AC 的第一步。也许你会发现这样一个现象：NN 为奇数的时候 Alice（先手）必败，NN 为偶数的时候 Alice 必胜。 这个猜想是否正确呢？下面我们来想办法证明它。
     *
     * 证明
     *
     * N = 1N=1 和 N = 2N=2 时结论成立。
     *
     * N > 2N>2 时，假设 N \leq kN≤k 时该结论成立，则 N = k + 1N=k+1 时：
     *
     * 如果 kk 为偶数，则 k + 1k+1 为奇数，xx 是 k + 1k+1 的因数，只可能是奇数，而奇数减去奇数等于偶数，且 k + 1 - x \leq kk+1−x≤k，故轮到 Bob 的时候都是偶数。而根据我们的猜想假设 N\le kN≤k 的时候偶数的时候先手必胜，故此时无论 Alice 拿走什么，Bob 都会处于必胜态，所以 Alice 处于必败态。
     * 如果 kk 为奇数，则 k + 1k+1 为偶数，xx 可以是奇数也可以是偶数，若 Alice 减去一个奇数，那么 k + 1 - xk+1−x 是一个小于等于 kk 的奇数，此时 Bob 占有它，处于必败态，则 Alice 处于必胜态。
     *
     *
     *
     * @Date 2020-07-24
     * @Param [N]
     * @return boolean
     **/
    public boolean divisorGame(int N) {
        return N%2 == 0 ? true : false;
    }


    public int findPeakElement(int[] nums) {

        if(nums == null || nums.length <= 0){
            return 0;
        }

        return binarySearch(nums, 0, nums.length - 1);

    }

    public int binarySearch(int [] nums, int l, int r){

        if(l == r){
            return l;
        }
        int middle = (l + r) / 2;
        if(nums[middle] > nums[middle + 1]){
            return binarySearch(nums, l, middle);
        }else{
            return binarySearch(nums, middle + 1, r);
        }
    }


    /**
     * @author zlx
     * @desc 9. 回文数
     * 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
     *
     * 示例 1:
     *
     * 输入: 121
     * 输出: true
     * 示例 2:
     *
     * 输入: -121
     * 输出: false
     * 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
     * 示例 3:
     *
     * 输入: 10
     * 输出: false
     * 解释: 从右向左读, 为 01 。因此它不是一个回文数。
     * 进阶:
     *
     * 你能不将整数转为字符串来解决这个问题吗？
     *
     *
     *  进阶思路： x<0 非回文数字， x的个位为0 非回文数字； 反转一半的数字， x%10 回去数字x的各个位置的数字， x%10 * 10 + （x/10）%10 循环此操作可以得到反转的数字，
     *           反转一半的边界是 x <= reverseNum 停止
     * @date  2020-06-10
     * @param x
     * @return boolean
     **/
    public boolean isPalindrome(int x) {

//        if(x < 0){
//            return false;
//        }
//        String a = String.valueOf(x);
//        int start = 0, end = a.length() - 1;
//        while(start != end){
//
//            if(a.charAt(start) != a.charAt(end)){
//                return false;
//            }
//            start ++;
//            end --;
//        }
//        return true;


        if(x < 0 || (x % 10 == 0 && x != 0)){
            return false;
        }
        int reverseNum = 0;
        while (x > reverseNum){

            reverseNum = reverseNum * 10 + x % 10;
            x = x/10;
        }

        return x == reverseNum || x == reverseNum / 10;
    }


    /**
     * @author zlx
     * @desc 面试题64. 求1+2+…+n
     * 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
     *
     *
     *
     * 示例 1：
     *
     * 输入: n = 3
     * 输出: 6
     * 示例 2：
     *
     * 输入: n = 9
     * 输出: 45
     *
     * 解题思路： 以递归为求解思路
     * @date  2020-06-02
     * @param n
     * @return int
     **/
    public int sumNums(int n) {

       boolean flag = n > 0 && ( n+= sumNums(n - 1)) > 0;
       return n;
    }

    /**
     * medium
     * @desc 1248. 统计「优美子数组」
     * 给你一个整数数组 nums 和一个整数 k。
     *
     * 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
     *
     * 请返回这个数组中「优美子数组」的数目。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1,1,2,1,1], k = 3
     * 输出：2
     * 解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
     * 示例 2：
     *
     * 输入：nums = [2,4,6], k = 1
     * 输出：0
     * 解释：数列中不包含任何奇数，所以不存在优美子数组。
     * 示例 3：
     *
     * 输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
     * 输出：16
     * @date 2020-04-21
     * @param nums
     * @param k
     * @return int
     *
     * 解题思路：
     * 这个题目中偶数其实是没有用的，我们可以单独建立一个 odd 数组来记录第 i 个奇数的下标。
     * 那么我们可以枚举奇数，假设当前枚举到第 i 个 那么[odd[i+k-1],odd[i+k]] 包含k个奇数，由于奇数中间存在偶数，一定存在其他子数组【l, r】包含 [odd[i+k-1],odd[i+k]]，且满足奇数个数为k个；
     *
     * odd[i] 表示第i个奇数的在nums中的位置index， 因此(odd[i-1],odd[i])之间都是偶数，同理（odd[i+k],odd(i+k-1)）之间也是偶数，
     * 因此，可以存在l属于（odd[i-1], odd[i]）, r属于（odd[i+k-1], odd[i+k]）, 子数组[l,r]， ,[odd[i+k],odd[i + k - 1]]且 [l,r] 里的奇数个数为 k 个，那么这个需要怎么统计呢？
     *
     * (odd[i] - odd[i-1]) * (odd[i+k] - odd[i + k - 1]);
     *
     *
     * 链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays/solution/tong-ji-you-mei-zi-shu-zu-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     *
     **/
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length;
        int res = 0;
        int [] odd = new int[n + 2];
        int cnt = 0;
        for(int i = 0;i < n;i++){
            if(nums[i] % 2 == 1){
                odd[++cnt] = i;
            }
        }
        odd[0] = -1;
        odd[++cnt] = n;
        System.out.println("====" + Arrays.toString(odd));
        System.out.println("cnt is:=====" + cnt);
        for(int i = 1;i + k <= cnt;i++){
            res += (odd[i] - odd[i-1]) * (odd[i+k] - odd[i + k - 1]);
        }
        return res;
    }

    /**
     * 233. 数字 1 的个数
     * 给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
     *
     * 示例:
     *
     * 输入: 13
     * 输出: 6
     * 解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。
     *
     * 解法一之暴力法： 从1到n遍历，分别计算各个数包含的1个数，再求和； （超时）
     *
     * 解法二：
     * 通过上面的列举我们可以发现，100以内的数字，除了10-19之间有11个‘1’之外，其余都只有1个。如果我们不考虑[10, 19]区间上那多出来的10个‘1’的话，
     * 那么我们在对任意一个两位数，十位数上的数字(加1)就代表1出现的个数，这时候我们再把多出的10个加上即可。比如56就有(5+1)+10=16个。如何知道是否要加上多出的10个呢，
     * 我们就要看十位上的数字是否大于等于2，是的话就要加上多余的10个'1'。那么我们就可以用(x+8)/10来判断一个数是否大于等于2。对于三位数区间 [100, 199] 内的数也是一样，
     * 除了[110, 119]之间多出的10个数之外，共21个‘1’，其余的每10个数的区间都只有11个‘1’，所以 [100, 199] 内共有21 + 11 * 9 = 120个‘1’。
     * 那么现在想想[0, 999]区间内‘1’的个数怎么求？根据前面的结果，
     * [0, 99] 内共有20个，[100, 199] 内共有120个，而其他每100个数内‘1’的个数也应该符合之前的规律，即也是20个，
     * 那么总共就有 120 + 20 * 9 = 300 个‘1’。那么还是可以用相同的方法来判断并累加1的个数
     *  (n + 8) /10 判断十位上的数字是否大于等于2
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/number-of-digit-one
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param n
     * @return
     */
    public static int countDigitOne(int n) {

        int res = 0, a = 1, b = 1;
        while(n > 0){
            res += (n + 8) /10 * a + (n % 10 == 1 ? 1 : 0) * b;
            System.out.println("res is: ===" + res);
            b += n % 10 * a;
            a *= 10;
            System.out.println("after operation a=" + a +" , b= " + b);
            n /= 10;
            System.out.println("n is: ====" + n);
        }
        return res;

    }



    public int countDigitOneSolutionI(int n) {

        int res = 0;
        for(int i =1; i <= n;i++){
            res += getOneCount(i);
        }
        return res;
    }

    public int getOneCount(int n){

        int res = 0;
        while (n != 0){
            int a = n % 10;
            n /= 10;
            if(a == 1){
                res +=1;
            }
        }
        return res;
    }


    public static int target = 6;


    /**
     * 793. 阶乘函数后K个零
     * @param K
     * @return
     * 例如， f(3) = 0 ，因为3! = 6的末尾没有0；而 f(11) = 2 ，因为11!= 39916800末端有2个0。给定 K，找出多少个非负整数x ，有 f(x) = K 的性质。
     *
     * 示例 1:
     * 输入:K = 0
     * 输出:5
     * 解释: 0!, 1!, 2!, 3!, and 4! 均符合 K = 0 的条件。
     *
     * 示例 2:
     * 输入:K = 5
     * 输出:0
     * 解释:没有匹配到这样的 x!，符合K = 5 的条件。
     *
     * K是范围在 [0, 10^9] 的整数。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/preimage-size-of-factorial-zeroes-function
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public static int preimageSizeFZF(int K) {

        if(K < 5){
            return 5;
        }
        int start = K - K/5;
        int ctn, val;
        while(start < K){
            ctn = start;
            val = start;
            while(val / 5 != 0){
                val /= 5;
                ctn += val;
            }
            if(ctn == K)
                return 5;
            else if(ctn > K)
                return 0;
            else
                start++;

        }
        return  0;
    }


    /**
     *172. 阶乘后的零
     * 给定一个整数 n，返回 n! 结果尾数中零的数量。
     *
     * 示例 1:
     *
     * 输入: 3
     * 输出: 0
     * 解释: 3! = 6, 尾数中没有零。
     * 示例 2:
     *
     * 输入: 5
     * 输出: 1
     * 解释: 5! = 120, 尾数中有 1 个零.
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * 思路：分析：
     * 一般类似的题目都会蕴含某种规律或简便方法的阶乘末尾一个零表示一个进位，则相当于乘以10而10 是由2*5所得，在1~100当中，可以产生10的有：0 2 4 5 6 8 结尾的数字，显然2是确定的，因为4、6、8当中都含有因子2，所以都可看当是2，那么关键在于5的数量了那么该问题的实质是要求出1~100含有多少个5由特殊推广到一般的论证过程可得：
     * 1、 每隔5个，会产生一个0，比如 5， 10 ，15，20.。。
     * 2 、每隔 5×5 个会多产生出一个0，比如 25，50，75，100
     * 3 、每隔 5×5×5 会多出一个0，比如125.
     *
     * 所以100！末尾有多少个零为：100/5+100/25=20+4=24那么1000！末尾有多少个零呢？同理得： 1000/5+1000/25+1000/125=200+40+8=248
     * 到此，问题解决了，但我们在学习过程中应当学会发散思维、举一反三。
     *
     * 接着，请问N！的末尾有多少个零呢？
     * 其实 也是同理的
     * N/5+N/25+……
     * @param n
     * @return
     */
    public int trailingZeroes(int n) {

        int k = 0;
        while (n != 0){
            k += n/5;
            n = n /5;
        }
        return k;
    }



    /**
     *
     * @param n
     * @return
     */
    public static int guessNumber(int n){
        int start = 1;
        int end = n;
        while(start < end){
            int middle = start + (end - start) / 2;
            //System.out.println("start:" + start + " end: " + end + "  middle: "+ middle);
            int tmp = guess(middle);
            if(tmp == 0){
                return middle;
            }else if(tmp == 1){
                start = middle + 1;
            }else{
                end = middle;
            }
        }
        return start;
    }


    /**
     * 常规的二分查找，会超时
     * @param n
     * @return
     */
    public static int guessNumber2(int n) {

        int start = 1;
        int end = n;
        while(start != end){
            int middle = (start + end) / 2;
            int tmp = guess(middle);
            if(tmp == 0){
                return middle;
            }else if(tmp == -1){
                start = middle + 1;
            }else{
                end = middle - 1;
            }
        }
        return start;

    }



    public static int middleFind(int start, int end){

        int middle = (start + end) / 2;
        int tmp = guess(middle);
        if(tmp == 0){
            return middle;
        }else if(tmp == 1){
            return middleFind(middle+1, end);
        }else{
            return middleFind(start, middle - 1);
        }
    }

    public static int guess(int n){

        if(n == target){
            return 0;
        }else if(n > target){
            return -1;
        }else{
            return 1;
        }
    }

    /**
     * 375. 猜数字大小 II
     * 我们正在玩一个猜数游戏，游戏规则如下：
     *
     * 我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。
     *
     * 每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。
     *
     * 然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。
     *
     * 示例:
     *
     * n = 10, 我选择了8.
     *
     * 第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
     * 第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
     * 第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。
     *
     * 游戏结束。8 就是我选的数字。
     *
     * 你最终要支付 5 + 7 + 9 = 21 块钱。
     * 给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param n
     * @return
     */
    public int getMoneyAmount(int n) {
        if(n == 0){
            return 0;
        }

        return 0;
    }

    /**
     *
     * @param n
     * @return
     */
    public static int arrangeCoins(int n) {

        //求解一元二次方程
        return (int) (-1 + Math.sqrt(1 + 8 * (long) n)) / 2;
        //超时
        /*int sum = 0;
        int level = 1;
        while(sum + level <= n){
            sum += level;
            level ++;
            System.out.println("level: " + level + "   sum: " + sum);
        }
        return level - 1;*/
    }


    /**
     * 313. 超级丑数
     * 编写一段程序来查找第 n 个超级丑数。
     *
     * 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
     *
     *
     * 解题思路：参考263第n个丑书求解
     * @param n
     * @param primes
     * @return
     */
    public static int nthSuperUglyNumber(int n, int[] primes) {

        if(n <= 1){
            return n;
        }
        int [] pointer = new int[primes.length];
        int [] res = new int[n];
        res[0] = 1;

        for(int i =1;i < n;i++){
            List<Integer> sameIndex = new ArrayList<>();
            int min = Integer.MAX_VALUE;
            int pointerIndex = 0;
            for(int j = 0;j < primes.length;j++){
                if(pointer[j] > n){
                    continue;
                }
                int tmp = primes[j] * res[pointer[j]];
                if(tmp < min){
                    min = tmp;
                    pointerIndex = j;
                }else if(tmp == min){
                    sameIndex.add(j);
                }

            }
            System.out.println();
            System.out.println("pointerIndex is: " + pointerIndex);
            System.out.println();
            pointer[pointerIndex] ++;
            if(!sameIndex.isEmpty()){
                for(Integer index: sameIndex){
                    pointer[index] ++;
                }
            }
            for(int z = 0; z< primes.length;z++){
                System.out.print(pointer[z] + "  ");
            }
            System.out.println();
            res[i] = min;
        }
        for(int i =0;i < n;i++){
            System.out.print(res[i] + "  ");
        }
        System.out.println();
        return res[n-1];
    }


    /**
     * 263. 丑数
     * 丑数就是只包含质因数 2, 3, 5 的正整数。
     * 1是丑书，0不是
     * @param num
     * @return
     */
    public boolean isUgly(int num) {

        if(num == 0){
            return false;
        }

        for(int i = 2;i<=5;i++){
            while(num % i == 0){
                num /=i;
            }
        }

        return num == 1;
    }

    /**
     * 264. 丑数 II
     * 编写一个程序，找出第 n 个丑数。
     *
     * 丑数就是只包含质因数 2, 3, 5 的正整数。
     *
     * 示例:
     *
     * 输入: n = 10
     * 输出: 12
     * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
     *
     * 解题思路： 创建3指针k0,k1,k2,
     * We have an array k of first n ugly number. We only know, at the beginning, the first one, which is 1. Then
     *
     * k[1] = min( k[0]x2, k[0]x3, k[0]x5). The answer is k[0]x2. So we move 2's pointer to 1. Then we test:
     *
     * k[2] = min( k[1]x2, k[0]x3, k[0]x5). And so on. Be careful about the cases such as 6, in which we need to forward both pointers of 2 and 3.
     *
     * x here is multiplication.
     *
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {

        if(n <= 6){
            return n;
        }
        int [] res = new int [n];
        int k0 = 0;
        int k1 = 0;
        int k2 = 0;
        res[0] = 1;
        for(int i = 1;i < n;i++){

            res[i] = Math.min(res[k0] * 2, Math.min(res[k1] * 3, res[k2] * 5));
            if(res[i] == res[k0] * 2)
                k0 ++;
            if(res[i] == res[k1] * 3)
                k1 ++;
            if(res[i] == res[k2] * 5)
                k2 ++;
        }
        return res[n-1];
    }
}
